import java.util.HashMap;
import java.util.Map;

public class Solution {
    public int longestSubsequence(int[] arr, int difference) {//会超时
        int len = arr.length;

        //以i为结尾的最长等差子序列的长度
        int[] dp = new int[len];

        for (int i = 0; i < len; i++) {
            dp[i] = 1;
        }

        for (int i = 1; i < len; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[i] - arr[j] == difference) {
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
                }
            }
        }

        int ret = 0;
        for (int num : dp) {
            ret = Math.max(ret, num);
        }
        return ret;
    }

    public int longestSubsequence2(int[] arr, int difference) {
        int len = arr.length;

        //以i为结尾的最长等差子序列的长度
        //以哈希表代替dp数组
        HashMap<Integer, Integer> map = new HashMap<>();//key为arr的值，value为dp的值

        map.put(arr[0], 1);

        for (int i = 1; i < len; i++) {
            map.put(arr[i], Math.max(map.getOrDefault(arr[i], 0), map.getOrDefault(arr[i] - difference, 0) + 1));

            if (map.getOrDefault(arr[i], 0) == 0) {
                map.put(arr[i], 1);
            }
        }

        int ret = 0;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            ret = Math.max(ret, entry.getValue());
        }
        return ret;
    }
}
